package primary.primary0;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class S0215数组中的第k个最大元素 {
    public static void main(String[] args) throws IOException {
        int[] nums;
        FileInputStream file = new FileInputStream("leetCode1/src/main/java/笔试做题/text1.txt");
        InputStreamReader reader = new InputStreamReader(file);
        BufferedReader bufferedReader = new BufferedReader(reader);

        String line;
        line = bufferedReader.readLine();
        String[] split = line.split(",");
        nums = new int[split.length];
        for(int i = 0; i < split.length; i++){
            nums[i] = Integer.parseInt(split[i]);
        }
//        Arrays.sort(nums);
//        System.out.println(nums[nums.length - 4124]);

        System.out.println(new Solution2().findKthLargest(nums, 4123));
    }

    static class Solution2 {
        /**
         * 75，非常值得一看
         * 手动实现一下堆，堆排序，记住每次操作都是取堆的根扔掉，然后取最后一个元素放到根，然后下沉，所以如果是k个最大值，那么要扔掉的就是小的值，也就是要一个小根堆
         * 堆就三个操作
         * 1. 堆的创建
         * 2. 堆的插入
         * 3. 堆的取出
         * 底层其实就两个操作，上浮和下沉
         */
        public int findKthLargest(int[] nums, int k) {
            if(nums == null || nums.length == 0){
                return -1;
            }
            if(nums.length == 1){
                return nums[0];
            }

            // 小根堆，找第k个最大值是用的小根堆，因为我们取的话只能取根，所以要逐个过滤小的，是小根堆
            // int[] heap = new int[k + 1];
            // 尝试原地换，不搞额外空间
            // 堆里就k个值，如果用k+1个，那么边界值特别麻烦，k可能和nums一样长
            for(int i = 0; i < k; i++){
                up(nums, i, i);
            }
            // 上面up注释掉，只用down，然后从 k/2 -> 0 都走一遍，也行。这种建队的方式原理是，如果左右子树都是堆，那我当前点下沉操作走通了之后，当前点+左右子树，形成的新树，也是堆。
//            for (int i =  k / 2; i >= 0; --i) {
//                down(nums, i, k);
//            }
            // 每次把第k大的值换成新的值，重新跑一遍
            for(int i = k; i < nums.length; i++){
                if(nums[i] > nums[0]){
                    swap(nums, 0, i);
                    down(nums, 0, k);
                }
                // System.out.println(Arrays.toString(nums));
            }
            return nums[0];
            // return Math.min(nums[1], nums[2]);
        }

        private void up(int[] nums, int curLoc, int endLoc){
            if(curLoc == 0){
                return;
            }
            // mark: 他妈的原来这里忘了-1，看了两个小时
            int parentLoc = (curLoc - 1) / 2;
            // 小的浮上去
            if(nums[parentLoc] > nums[curLoc]){
                swap(nums, parentLoc, curLoc);
                up(nums, parentLoc, endLoc);
            }
        }

        private void down(int[] nums, int curLoc, int endLoc){
            int l = curLoc * 2 + 1;
            int r = curLoc * 2 + 2;
            int minLoc = curLoc;
            if(l < endLoc && nums[l] < nums[minLoc]){
                minLoc = l;
            }
            if(r < endLoc && nums[r] < nums[minLoc]){
                minLoc = r;
            }
            if(minLoc != curLoc){
                swap(nums, curLoc, minLoc);
                down(nums, minLoc, endLoc);
            }
//
//            if(l >= endLoc){
//                return;
//            }
//            if(endLoc == r){
//                if(nums[l] < nums[curLoc]){
//                    swap(nums, l, curLoc);
//                }
//            }else{
//                // 两个子节点都在范围内
//                if(nums[l] < nums[curLoc] && nums[l] <= nums[r]){
//                    swap(nums, l, curLoc);
//                    down(nums, l, endLoc);
//                }else if(nums[r] < nums[curLoc] && nums[r] <= nums[l]){
//                    swap(nums, r, curLoc);
//                    down(nums, r, endLoc);
//                }
//            }
        }

        private void swap(int[] nums, int locA, int locB){
            int temp = nums[locA];
            nums[locA] = nums[locB];
            nums[locB] = temp;
        }
    }

    class Solution {
        /**
         * 31
         * 第k大总让我想起堆，复杂度nlogk，但是k和n差不多大，具体体现在运算上会不会不算O(n)
         */
        public int findKthLargest(int[] nums, int k) {
            // 小根堆，找第k个最大值是用的小根堆，因为我们取的话只能取根，所以要逐个过滤小的，是小根堆
            Queue<Integer> minHeap = new PriorityQueue(new Comparator<Integer>(){
                @Override
                public int compare(Integer a, Integer b){
                    return a - b;
                }
            });
            int loc = 0;
            while(--k >= 0){
                minHeap.offer(nums[loc]);
                loc ++;
            }
            while(loc < nums.length){
                minHeap.offer(nums[loc]);
                minHeap.poll();
                loc ++;
            }
            return minHeap.peek();
        }
    }
}
